The prior art will now be described with reference to the following drawings in which:
FIG. 1 is a schematic view of a conventional single pixel of a CRT type display;
FIGS. 2(1) to 2(5) are schematic views of a 2.times.2 dithering process;
FIG. 3 is an illustration of the dithering process; and
FIG. 4 is an illustration of an artifact producing matrix.
Colour raster graphic display devices are well known in the art. The display of colour images in these devices is normally achieved by means of a pixel map comprising individual pixels. These pixels in turn consist of a collection of bits which represent the colour value of that pixel on the display device. The number of different possible bits in this collection corresponds with the number of different colours which may be displayed by the display device and hence the fidelity with which the device can display a given picture. Common colour systems store 8 or 24 bits per pixel, although other variations are possible.
A display device displays the corresponding colour value of the pixel, often to a high resolution. Common screen displays are capable of displaying a number of different pixels in the range of 1280 by 1024 pixels with each pixel capable of displaying up to 2.sup.24 different colour values.
Colours are often displayed on a computer display according to a particular model. The red, green, blue (RGB) colour model is one that is in common use with Cathode Ray Tubes (CRT) and colour raster display devices. Other colour display models include cyan, magenta, yellow (CMY) often used in colour-printing devices. An example of the RGB model is in the NTSC picture display standard in common use with computer displays. In this standard, each pixel element is divided into 3 separate sub-groupings. These separate subgroupings represent the Red, Green and Blue portion of a given pixel element respectively.
Referring now to FIG. 1, the viewing surface of a colour CRT often consists of closely spaced pixels 20. Each pixel can be made up of a red 21, green 22 and blue 23 phosphor dot or pixel elements. These dots are so small that light emanating from the individual dots is perceived by the viewer as a mixture of the corresponding three colours. A wide range of different colours can thus be produced by a pixel element by variation of the strength with which each phosphor dot is excited. A conversion arrangement (not illustrated) is normally provided so that the strength of each phosphor dot's excitation has some proportionality to the value of each of the above mentioned pixel element subgrouping. By way of example, a 24 bits per pixel colour display system divided into 8 bits for each of the three colours red, green and blue will be assumed. This corresponds to 2.sup.8 or 256 separate intensity levels of each of red, green and blue respectively and 2.sup.24 different colour values. A colour display capable of displaying this many colours can approximate a continuous tone image to such a degree that for all practical purposes the display can be considered to be a continuous tone display.
Many display devices are unable to actually display the full range of colours provided by, for example, a 24 bit input pixel. For example, a black and white raster image display can only display 2 colours, namely black and white and is known as a bi-level device. Other colour display devices can only display a finite number of discrete intensity levels for each colour unit. By way of further example, in a colour bi-level device, such as a ferroelectric liquid crystal display (FLCD), each dot on the screen can be at just two intensity levels, either fully on or fully off.
If the display device receives an input which has been generated on the basis that each pixel is able to display a larger number of intensity levels than can actually be displayed, then there will be an error in the colour displayed, being the difference between the exact pixel value required to be displayed and the approximated value actually displayed.
Methods of generating input signals to displays have been developed to increase the number of colours displayable on an discrete colour display device such as a bi-level colour display by grouping pixels together. The methods used are known generally as halftoning. For an explanation of the different aspects of halftoning the reader is referred to the book `Digital Halftoning` by Robert Ulichney, published in 1991 by MIT Press.
FIGS. 2 and 3 show one such method, called dithering, used for increasing the number of intensity levels. In this example, the pixel arrangement of FIG. 1 of the display screen is grouped together into a 2.times.2 pixel area 24. The 2.times.2 pixel area 24 of a bi-level display is used to produce five separate intensity levels for each primary colour by selectively turning on an individual primary pixel. These levels range from a lowest level shown in FIG. 2(1), a first level of brightness shown in FIG. 2(2), a second level brightness shown in FIG. 2(3), a third level shown in FIG. 2(4) and a fourth level shown in FIG. 2(5), giving a total of 5 levels. In general, a grouping of n pixel elements will be able to produce a maximum of n+1 separate intensity levels for each primary colour.
For ease of understanding, the discussion will proceed in relation to a bi-level display capable of displaying only a single primary colour, namely black or white. Those skilled in the art will however appreciate that the same principles can be applied to a display having multiple primary colours by treating each primary colour separately, independent of the other primary colours that a given display is using. Additionally, the discussion can also be applied to a display, where each individual element has multiple intensity levels through the grouping together of n+1 separate intensity levels.
In the method of dithering an image, the decision to intensify a particular point on the screen O(x,y) is made dependent on the desired intensity S(x,y) at that particular point and on a predetermined dither matrix value D(i,j). To display the required point at O(x,y), it is necessary to generate EQU i=x modulo n (EQ 1) EQU j=y modulo m (EQ 2)
Where x and y are the pixel positions and n and m are the desired lengths and widths of the dither Matrix D. Then, if S(x,y)&gt;D(i,j), the point at O(x,y) is intensified, otherwise it is not. An example of this process is shown in FIG. 3. Input matrix 30 containing S(x,y), and dither matrix 30 containing locations D(i,j) 31, are used in conjunction with the above display intensification rule to produce output matrix elements O(x,y) with 0 corresponding to those points that are not intensified, and 1 corresponding to those points that are intensified. Hence, input element S(0,0) with a value of 0, will be compared with D(0,0) which has a value 0 also, and the comparison determination is not satisfied, so the point O(0,0) will not be intensified. Input element S(2,3) with a value of 3, will be matched with dither matrix element D(0,1) since 2 modulo 2=0 and 3 modulo 2=1. D(0,0) has a value 1, so the output element O(2,3) is iilluminated and so on.
The above example is a sample operation of a dither matrix of size 2.times.2 elements, for a black and white display. The choice of particular values of a dither matrix, although somewhat arbitrary, is determined by a number of important factors including:
1. The display device which is to display the image. Some devices, such as laser printers and film recorders, are poor at reproducing isolated `on` pixels and hence dither matrix elements must be chosen such that output matrix elements are clustered together as much as possible. Such choices are known by the name `clustered-dot ordered dither`.
2. The need to avoid the introduction of visual artifacts. It is common for an output image to display regions of equal or slowly varying intensities of a particular colour. Certain permutations of matrix values will result in artifacts such as lines appearing when displaying these areas. Referring now to FIG. 4, a 3.times.3 dither matrix 33 is shown illustrated which results in horizontal lines appearing in any large area of the image which had an intensity equal to 3.
3. Preferably the dither matrix should encompass all the values in the range 0 to the maximum value desired to be output. For example common computer systems store images as 8 bit levels for each primary colour. Hence a dither matrix that includes 256 different values is desirable to increase the `granularity` of displayable values. Additionally, with larger matrices, it is desirable to repeat each value multiple times.
By increasing the number of pixels grouped together for use with a dither matrix, it is not readily apparent how to assign values to the dither matrix. For example, if the size of the dither matrix is of the order of 60.times.68 elements, there will be 4,080 possible intensity value elements in the dither matrix which must be assigned.
U.S. Pat. No. 5,214,517 by Sullivan discloses one method of halftoning an image by means of multilevel correlated minimal visual noise binary patterns created through a process known as simulated annealing and using a separate halftone bit pattern memory for each possible level of input, thereby resulting in a substantial increase in the necessary pattern storage space. The present invention relies on the creation of a standard dither matrix rather than multiple level bit patterns in addition to disclosing the use of methods different to those disclosed in the Sullivan patent.
It is an object of the present invention to provide an improved method of displaying images on a discrete level output display by providing a process whereby the intensity value elements in the dither matrix can be advantageously assigned.